#include "pairheap.h"
#include "fatal.h"
#include <stdlib.h>

struct PairNode {
	ElementType Element;
	Position LeftChild;
	Position NextSibling;
	Position Prev;
};

#define MaxSiblings 1000

Position CompareAndLink(Position First, Position Second);
PairHeap CombineSiblings(Position FirstSibling);

PairHeap Initialize(void) {
	return NULL;
}

PairHeap MakeEmpty(PairHeap H) {
	if (H != NULL) {
		MakeEmpty(H->LeftChild);
		MakeEmpty(H->NextSibling);
		free(H);
	}
	return NULL;
}

/* START: fig12_54.txt */
/* Insert Item into pairing heap H */
/* Return resulting pairing heap */
/* A pointer to the newly allocated node */
/* is passed back by reference and accessed as *Loc */

PairHeap Insert(ElementType Item, PairHeap H, Position *Loc) {
	Position NewNode;

	NewNode = malloc(sizeof(struct PairNode));
	if (NewNode == NULL)
		FatalError("Out of space!!!");
	NewNode->Element = Item;
	NewNode->LeftChild = NewNode->NextSibling = NULL;
	NewNode->Prev = NULL;

	*Loc = NewNode;
	if (H == NULL)
		return NewNode;
	else
		return CompareAndLink(H, NewNode);
}

/* Lower item in Position P by Delta */

PairHeap DecreaseKey(Position P, ElementType Delta, PairHeap H) {
	if (Delta < 0)
		Error("DecreaseKey called with negative Delta");

	P->Element -= Delta;
	if (P == H)
		return H;

	if (P->NextSibling != NULL)
		P->NextSibling->Prev = P->Prev;
	if (P->Prev->LeftChild == P)
		P->Prev->LeftChild = P->NextSibling;
	else
		P->Prev->NextSibling = P->NextSibling;

	P->NextSibling = NULL;
	return CompareAndLink(H, P);
}
/* END */

/* START: fig12_55.txt */
PairHeap DeleteMin(ElementType *MinItem, PairHeap H) {
	Position NewRoot = NULL;

	if (IsEmpty(H))
		Error("Pairing heap is empty!");
	else {
		*MinItem = H->Element;
		if (H->LeftChild != NULL)
			NewRoot = CombineSiblings(H->LeftChild);
		free(H);
	}
	return NewRoot;
}
/* END */

/* START: fig12_53.txt */
/* This is the basic operation to maintain order */
/* Links First and Second together to satisfy heap order */
/* Returns the resulting tree */
/* First is assumed NOT NULL */
/* First->NextSibling  MUST be NULL on entry */

Position CompareAndLink(Position First, Position Second) {
	if (Second == NULL)
		return First;
	else if (First->Element <= Second->Element) {
		/* Attach Second as the leftmost child of First */
		Second->Prev = First;
		First->NextSibling = Second->NextSibling;
		if (First->NextSibling != NULL)
			First->NextSibling->Prev = First;
		Second->NextSibling = First->LeftChild;
		if (Second->NextSibling != NULL)
			Second->NextSibling->Prev = Second;
		First->LeftChild = Second;
		return First;
	} else {
		/* Attach First as the leftmost child of Second */
		Second->Prev = First->Prev;
		First->Prev = Second;
		First->NextSibling = Second->LeftChild;
		if (First->NextSibling != NULL)
			First->NextSibling->Prev = First;
		Second->LeftChild = First;
		return Second;
	}
}
/* END */

/* START: fig12_56.txt */
/* Assumes FirstSibling is NOT NULL */

PairHeap CombineSiblings(Position FirstSibling) {
	static Position TreeArray[MaxSiblings];
	int i, j, NumSiblings;

	/* If only one tree, return it */
	if (FirstSibling->NextSibling == NULL)
		return FirstSibling;

	/* Place each subtree in TreeArray */
	for (NumSiblings = 0; FirstSibling != NULL; NumSiblings++) {
		TreeArray[NumSiblings] = FirstSibling;
		FirstSibling->Prev->NextSibling = NULL; /* Break links */
		FirstSibling = FirstSibling->NextSibling;
	}
	TreeArray[NumSiblings] = NULL;

	/* Combine the subtrees two at a time, */
	/* going left to right */
	for (i = 0; i + 1 < NumSiblings; i += 2)
		TreeArray[i] = CompareAndLink(TreeArray[i], TreeArray[i + 1]);

	/* j has the result of the last CompareAndLink */
	/* If an odd number of trees, get the last one */
	j = i - 2;
	if (j == NumSiblings - 3)
		TreeArray[j] = CompareAndLink(TreeArray[j], TreeArray[j + 2]);

	/* Now go right to left, merging last tree with */
	/* next to last. The result becomes the new last */
	for (; j >= 2; j -= 2)
		TreeArray[j - 2] = CompareAndLink(TreeArray[j - 2], TreeArray[j]);

	return TreeArray[0];
}
/* END */

ElementType FindMin(PairHeap H) {
	if (!IsEmpty(H))
		return H->Element;
	Error("Priority Queue is Empty");
	return 0;
}

int IsEmpty(PairHeap H) {
	return H == NULL;
}

int IsFull(PairHeap H) {
	return 0; /* Never full */
}

void Destroy(PairHeap H) {
	MakeEmpty(H);
}

